package com.algorithm.lzr.array;


import com.sun.tools.javac.util.Assert;

import java.util.HashSet;

/**
 * @Title: LongestConsecutive
 * @Package com.algorithm.lzr.array
 * @Author liu.zr 2019-07-16 17:42
 * @Description: <从数组中查找最长的连续元素>
 */
public class LongestConsecutive {

    public static void main(String[] args) {
        int[] array = new int[]{1, 1, 2, 3, 5, 5, 7, 8};
        Assert.check(longestConsecutive(array) == 3);
    }


    public static int longestConsecutive(int[] array) {
        HashSet<Integer> set = new HashSet<>(array.length);
        for (int i : array) set.add(i);
        int longest = 0;
        for (int i : array) {
            int length = 1;
            // 当前值是否有前一个连续的值
            for (int j = i - 1; set.contains(j); --j) {
                set.remove(j);
                ++length;
            }
            // 当前值是否有后一个连续的值
            for (int j = i + 1; set.contains(j); ++j) {
                set.remove(j);
                ++length;
            }
            longest = Math.max(longest, length);
        }
        return longest;
    }

}
